Exercici 3 (Tasca 3).
(pumping lemma,
hard exercise)
Sobre as en la primera part i bs en la segona
Donat k\in \mathbb N, demostreu que L_k=\{xy\in \{a,b\}^* \mid |x|_a=k|y|_b\} és regular si i només si k=1 o k=0.
Ajut
La part difícil és demostrar que per a k>1, el llenguatge L_k no és regular. Penseu primer en k=2. L’argument per a una k genèrica és una simple generalització d’aquest cas.
Més ajut
Considereu el revessat de L_2.